package com.learn.algorlthm;


import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 重建二叉树
 * 根据二叉树的前序遍历和中序遍历的结果，重建出该二驻树。假设输入的前序遍历和中序遍历的结果都不含重复的数字
 */
public class Learn07 {

    /**
     * preorder = [3, 9, 20, 15, 7]
     * inorder = [9, 3 ,15, 20, 7]
     *
     * 解题思路
     * 前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树
     * 的右子树中序遍历的结果
     */

    public static int[] preorder = {3, 9, 20, 15, 7};
    public static int[] inorder = {9, 3 ,15, 20, 7};


    private static Map<Integer, Integer> inorderIndex = new HashMap<>();

    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        for (int i = 0; i < in.length; i++) {
            inorderIndex.put(in[i], i);

        }

        return reConstructBinaryTree(pre, 0, pre.length -1,
                in, 0, in.length - 1);
    }

    private static TreeNode reConstructBinaryTree(int[] pre, int preL, int preR,
                                                  int[] in, int inL, int inR) {
        if (preL > preR)
            return null;

        TreeNode root = new TreeNode(pre[preL]);
        Integer _inorderIndex = inorderIndex.get(pre[preL]);

        Integer leftTreeSize = _inorderIndex - inL;
        root.left = reConstructBinaryTree(pre, preL +1 , preL + leftTreeSize,
                in, inL, inL + leftTreeSize - 1);

        root.right = reConstructBinaryTree(pre, preL + leftTreeSize +1 , preR,
                in, inL + leftTreeSize + 1, inR );

        return root;
    }

    //engrion   扩展 -> 二叉树先序遍历，中序遍历， 后序遍历

    /**
     * 扩展知识 -> 二叉树的先序遍历
     */
    public static void preRecursion(TreeNode treeNode) {
        System.out.println(treeNode.value);
        if (treeNode.left != null)
            preRecursion(treeNode.left);
        if (treeNode.right != null)
            preRecursion(treeNode.right);
    }

    /**
     * 扩展知识 -> 二叉树的中序遍历
     */
    public static void inResursion(TreeNode treeNode) {
        if (treeNode != null) {
            inResursion(treeNode.left);
            System.out.println(treeNode.value);
            inResursion(treeNode.right);
        }

    }
    /**
     * 扩展知识 -> 二叉树的后序遍历
     */
    public static void postResursion(TreeNode treeNode) {
        if (treeNode != null) {
            postResursion(treeNode.left);
            postResursion(treeNode.right);
            System.out.println(treeNode.value);
        }

    }
// https://blog.csdn.net/kerryfish/article/details/24309617

    /**
     *
     * @param treeNode
     * 利用栈实现循环先序遍历二叉树
     * 这种实现类似于图的深度优先遍历（DFS）
     * 维护一个栈，将根节点入桡，然后只要栈不为空，出栈并访问，接着依次将访问节点的右节点，左节点入栈
     * 这种方式应该是对先序遍历的一种特殊实现（看上去简单明了）,但是不具备很好的扩展性，在中序和后序方式中不适用
     */
    public static void preStack_1(TreeNode treeNode) {
        if (treeNode == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);
        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            System.out.println(temp.value);
            if (temp.right != null)
                stack.push(temp.right);
            if (temp.left != null)
                stack.push(temp.left);
        }
    }

    /**
     * 利用栈模拟递归过程实现循环先序遍历二叉树
     * 这种方式具备扩殿性，它模拟递归的过程，将左子树点不断的压入栈。直到null，然后处理栈顶节点的右子树
     * @param treeNode
     */
    public static void preStack_2(TreeNode treeNode) {
        if (treeNode == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        while (treeNode != null || !stack.isEmpty()) {
            while (treeNode != null) {
                System.out.println(treeNode.value);
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            treeNode = stack.pop();
            treeNode = treeNode.right;//如果是null，出栈并处理右子树
        }

    }

    /**
     *
     * @param treeNode
     * 利用栈模拟递归过程实现循环中遍历二叉树
     * 思想和上面的perStack_2相同，只是访问的时间是在左子树都处理完直到null的时候出栈并访问
     */
    public static void inStack(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (treeNode != null || !stack.isEmpty()) {
            while (treeNode != null) {
                stack.push(treeNode);//先访问再入栈
                treeNode = treeNode.left;
            }
            treeNode = stack.pop();
            System.out.println(treeNode.value);
            treeNode = treeNode.right;//如果是null，出栈并处理右子树
        }

    }

    /**
     *
     * @param treeNode
     * 后序遍历不同于先序和中序，它是要先处理完左右子树，然后同去处理根（回溯），所以需要一个记录哪些节点已经被访问的结构（可以在树结构里面加一个标记），这里可以用map实现
     */
    public static void postStack(TreeNode treeNode) {
        if(treeNode==null)
            return;
        Stack<TreeNode> s=new Stack<TreeNode>();
        Map<TreeNode,Boolean> map=new HashMap<TreeNode,Boolean>();

        s.push(treeNode);
        while(!s.isEmpty()){
            TreeNode temp=s.peek();
            if(temp.left!=null&&!map.containsKey(temp.left)){
                temp=temp.left;
                while(temp!=null){
                    if(map.containsKey(temp))
                        break;
                    else
                        s.push(temp);
                    temp=temp.left;
                }
                continue;
            }
            if(temp.right!=null&&!map.containsKey(temp.right)){
                s.push(temp.right);
                continue;
            }
            TreeNode t=s.pop();
            map.put(t,true);
            System.out.println(t.value);
        }
    }


    //endengrion


    static class TreeNode{
        public Integer value;

        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(Integer value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

}
